package DataStructure.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 94. 二叉树的中序遍历 https://leetcode.cn/problems/binary-tree-inorder-traversal/
 * 题目简述：给定一个二叉树的根节点root，返回它的中序遍历。
 * 中序遍历：左根右，即对于每一棵子树，先遍历其左子树，然后遍历其根节点，最后遍历其右子树
 */
public class InorderTraversal {

    /**
     * 思路一：递归遍历。先递归访问左子树，然后访问根节点，最后递归访问右子树
     */
    List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return result;
        inorderTraversal(root.left);
        result.add(root.val);
        inorderTraversal(root.right);
        return result;
    }

    /**
     * 思路二：非递归遍历。利用栈进行迭代遍历。指针一直向左走，经过就压入栈，直到指向null后pop访问(此时其左子树必定为null或者已经pop访问过了), 访问后开始遍历右子树
     * 1. pop访问的元素其左孩子必定已经pop过了
     * 2. pop访问元素后要迭代其右子树
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
        return result;
    }
}
